package 中等.其他;

/**
 * 给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
 * 我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
 * 所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
 * 请你返回「表现良好时间段」的最大长度。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-well-performing-interval
 */
public class 表现良好的最长时间段_1124 {

    public static void main(String[] args) {

        System.out.println(longestWPI(new int[]{9, 9, 6, 0, 6, 6, 9}));

    }

    /**
     * 前缀和+枚举
     */
    public static int longestWPI(int[] hours) {
        int maxLen = 0;
        int[] prefixSum = new int[hours.length];
        prefixSum[0] = hours[0] > 8 ? 1 : 0;
        for (int i = 1; i < prefixSum.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + (hours[i] > 8 ? 1 : 0);
        }

        for (int i = 0; i < prefixSum.length; i++) {
            // 贪心，如果前面是劳累的一天，那么以前面一天开始的时间是比当前开始的长度要长
            if (i > 0 && hours[i - 1] > 8) {
                continue;
            }
            for (int j = i; j < prefixSum.length; j++) {
                if ((prefixSum[j] - (i > 0 ? prefixSum[i - 1] :
                        0)) * 2 - (j - i + 1) > 0) {
                    maxLen = Math.max(maxLen, j - i + 1);
                }
            }
        }

        return maxLen;
    }

}
